The field of computer graphics concerns the creation, storage, manipulation and display of pictures and models of objects by a digital processor. Interactive computer graphics is the subclass of computer graphics in which a user dynamically controls the picture's content, format, size or color on a display surface by means of an interaction device such as a keyboard, lever or joystick. See Fundamentals of Interactive Computer Graphics, by J. D. Foley and A. Van Dam, ISBN: 0-201-14468-9. The creation of synthetic images (i.e., images which exist as abstract collections of lines, points, curves, etc., in the computer's memory) is the usual domain of interactive computer graphics.
The two primary classes of interactive computer graphics systems are random-scan and raster-scan systems. Images displayed by a random-scan system are encoded as commands to draw each output primitive (i.e., point, line or polygon) by plotting individual points or drawing connecting lines between specified starting and ending coordinates of line segments. Polygons are simply treated as a closed series of line segments. Encoding for a raster-scan system is much simpler: output primitives are broken up into their constituent points for display. The major difference between a simple point-plotting random-scan system and a raster-scan system is in the organization of the stored data used to drive the display. As explained below, the data is stored in a "frame buffer" (also called a "refresh buffer").
In the random-scan system the component points of each successive output primitive are stored sequentially in memory and plotted in the same order, one point at a time. This is because the beam may be moved randomly on the screen. In the raster-scan system the frame buffer memory is arranged as a 2-dimensional array of data. The value stored at a particular row and column encodes an intensity and/or color value of a corresponding display element on the screen. The location of each display element is typically specified by a unique (X,Y) coordinate. Since each memory location defines a single point-sized element of an image, both the display screen location and its corresponding memory location are often called a "pixel," short for "picture element." Hereinafter, to avoid confusion, the term "display pixel" will be used to indicate picture elements of a display device, and "storage pixel" to indicate memory locations corresponding to the display pixels.
FIG. 1 is a simplified block diagram of a raster-scan graphics system 10, which includes an image creation system 12, an image storage system 14 (such as a frame buffer), an image display system 16, a raster-scan display 18 and an interaction device 20. The image creation system 12 converts output primitives into the data stored in the frame buffer of the image storage system 14. The processing speed of the image creation system 12 establishes most of the characteristics of the overall raster-scan system 10. Moreover, the image creation system 12 is particularly malleable because it is typically implemented with a microprocessor. The overall speed at which the stored image data can be modified is dependent upon, among other things, how fast the image creation system executes instructions. It is the image creation system's execution of instructions which is often the slowest process in creating or changing an image. This is because the "scan conversion" algorithm (described below) typically requires many iterations. Usually, the faster the scan conversion algorithm, the faster the overall system response time to user commands. Moreover, it is known that response time is critical to user satisfaction and, more importantly, to user productivity.
The process of converting a mathematical representation of an image to the array of pixel data in the image storage system 14 is called "scan conversion." Scan conversion algorithms are always needed in a raster-scan graphics system and are usually carried out by the image creation system 12. The scan conversion algorithm is typically invoked hundreds or even thousands of times each time an image is created or modified; therefore, it must not only create visually pleasing images, but must also execute as rapidly as possible. Indeed speed versus image quality is the basic tradeoff inherent in known scan conversion algorithms. Some scan conversion algorithms are fast and create images with jagged edges, while others are slower and create images with smoother edges; however it can generally be said that faster is better for a given smoothness of image.
FIG. 2 depicts an exemplary line, y=mx+b, along with a vector 22 as it might be rendered (i.e., stored) in the frame buffer of the image storage system 14. Vector 22 is composed of a set of display pixels P.sub.0, P.sub.1, P.sub.2, . . . P.sub.N driven by a corresponding set of storage pixels in the frame buffer. Vector 22 is rendered by stepping along the major axis, in this case the X-axis, and computing corresponding minor axis (Y-axis) ordinate values. These (X,Y) coordinates define the storage and display pixels composing the vector 22. The basic task in scan converting a line is computing the integer coordinates of the display pixels lying nearest the line, determining the storage pixel addresses corresponding to those display pixels, and determining a value to assign to each storage pixel.
As can be seen from vector 22, the limited resolution of the frame buffer 14 and display device 18 causes the vector to become jagged, or "aliased." Techniques for generating antialiased (i.e., smooth) vectors are known in the art. See, e.g., Chapter 11.2.3 of Fundamentals of Interactive Computer Graphics, referenced above, and references cited therein for details of known antialiasing techniques. The problem with these known antialiasing techniques is that they are too slow for many applications.
FIGS. 3(a) and 3(c) depict two sets of vectors. The endpoint description of the set shown in FIG. 3(a) is a simple horizontal translation of the endpoint description of the set shown in FIG. 3(c). Both sets of vectors have a slope of 1/200. The vectors of FIG. 3(a) have been filtered, i.e., are antialiased, while the vectors of FIG. 3(c) are aliased. The spatial aliasing shown by the unfiltered set of vectors in FIG. 3(c) is not the only aliasing problem in computer generated graphics. Another aliasing problem is shown in FIGS. 3(b) and 3(d). The vectors in FIG. 3(b) are the same as those in FIG. 3(a), and the vectors in FIG. 3(d) are the same as those in FIG. 3(c), with the exception that the vectors in FIGS. 3(b) and 3(d) have been vertically translated one-half pixel. If these two sets of aliased and antialiased vectors are displayed as part of a real time series, the antialiased vectors will have the correct apparent motion, i.e., the antialiased vectors will appear to be slowly moving up, while the aliased vectors will appear to be quickly moving in the horizontal direction. The arrow in FIG. 3(d) points to a step in the displayed pixels, which is similar to the steps in FIG. 2, e.g., between P.sub.1 and P.sub.2 This step is noticeably offset from the step in FIG. 3(c). The motion of these steps dominate the apparent motion of the unfiltered vectors in the real time series. I.e., the image on the right will appear to move at the wrong speed and in the wrong direction. This artifact is called "aliasing-induced motion." A viewer sees a combination of all aliasing artifacts, including those due to both spatial aliasing and aliasing-induced motion. As pixel rendering speed increases and the goal of real-time generation of images is approached, aliasing-induced motion becomes greater and the total aliasing problem becomes more troublesome. See A. C. Barkans, "High Speed High Quality Antialiased Vector Generation," Computer Graphics, Vol. 24, Number 4, August 1990, which is incorporated herein by reference.
Users of interactive graphics systems now expect vector generation to be fast enough to support the real time display of user-controlled complex images. This has aggravated the aliasing problem since aliasing-induced motion is added to the formerly dominant static spatial aliasing. Most of the research into techniques for rendering antialiased vectors has focused on the use of "filtering" to remove the aliasing artifacts (which may be thought of as due to high frequency quantization "noise"). When filtering is used, the intensity of a display pixel is determined by the image brightness within a small area around the idealized line y=mx+b, not by the brightness at the pixel's center. Filtering is controlled by a "filter function" that describes the spatial distribution of light emitted by a display pixel; i.e., filtering is an averaging process, and the filter function in effect provides a weighting function for the averaging process. See, S. Gupta and R. F. Sproull, "Filtering Edges for Gray-Scale Displays," Proceedings of SIGGRAPH '81, Computer Graphics, Vol. 15, Number 3 (August 1981), wherein the authors suggest truncating the filter function so that a lookup table of filter values can be used, thus increasing scan conversion speed relative to the speed achievable by computing the filter values while rendering; however, using lookup tables as suggested by Gupta and Sproull still results in a decrease in scan conversion speed over rendering aliased vectors.
The numerical values that result from filtering are often thought of as intensity values; however, the use of intensity values places limitations on the usefulness of the vectors. In many applications it is necessary to compose the image with differently-colored vectors, each of which is shaded and/or depth-cued. (Depth cueing is a process designed to enhance a user's comprehension of three dimensional images by varying a pixel's intensity with the pixel's distance from the user's viewpoint.) The limitations inherent in storing intensity values may be removed by using "alpha" values in combination with color values to produce intensity values in rendering antialiased vectors. See T. Duff, "Compositing 3-D Rendered Images," Proceedings of SIGGRAPH '85, Computer Graphics, Vol. 19, Number 3 (July 1985). Elmquist combined using the alpha values of Duff in the filter table of Gupta. See A.C. Barkans, "High Speed High Quality Antialiased Vector Generation," Computer Graphics, Vol 24, No 4, August 1990, pg. 321. An important goal of the present invention is to provide a high speed solution to the problem of rendering antialiased vectors at speeds formerly achievable only when rendering aliased vectors. A further object of the present invention is to provide high speed hardware for rendering antialiased vectors (as opposed to the slower sequential software techniques that are known).